package dstbsort;

import java.util.Arrays;
import java.util.concurrent.*;

public class DstbMergeSort {

    /**
     * 将给定数组排序(多线程，归并排序)
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组 排序后的数组
     */

    private final static ExecutorService pool = new ThreadPoolExecutor(10000000, 1000000000, 100L, TimeUnit.SECONDS,
            new LinkedBlockingQueue<>());

    public static void main(String[] args) throws Exception {
        int total = 1000000;
        int[] list = new int[total];
        for (int i = 0; i < total; i++) {
            int rand = (int) (Math.random() * total);
            list[i] = rand;
        }
        long startTime = System.currentTimeMillis();
        sort(list);
        long end = System.currentTimeMillis();
        System.out.println(end - startTime);
    }

    public static int[] sort(final int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = sort(arr, 0, arr.length - 1, 0);
        pool.shutdown();
        return res;
    }

    private static int[] sort(final int[] arr, int start, int end, int k) {
        if (start > end) {
            return new int[]{};
        }
        if (start == end) {
            return new int[]{arr[start]};
        }
        if ((k >= 6) || (end - start <= 1000)) {
            int[] res = Arrays.copyOfRange(arr, start, end + 1);
            Arrays.sort(res);
            return res;
        }
        int mid = (end - start) / 2 + start;
        CompletableFuture<int[]> left = CompletableFuture.supplyAsync(() -> {
            return sort(arr, start, mid, k + 1);
        }, pool);
        CompletableFuture<int[]> right = CompletableFuture.supplyAsync(() -> {
            return sort(arr, mid + 1, end, k + 1);
        }, pool);
        CompletableFuture<int[]> res = left.thenCombineAsync(right, (a, b) -> {
            return merge(a, b);
        }, pool);
        return res.join();
    }

    private static int[] merge(int[] left, int[] right) {
        int lenL = left.length;
        int lenR = right.length;
        int len = lenL + lenR;
        int[] res = new int[len];
        int i = 0;
        int j = 0;
        int k = 0;
        while (i < lenL && j < lenR) {
            if (left[i] < right[j]) {
                res[k++] = left[i++];
            } else {
                res[k++] = right[j++];
            }
        }
        while (i < lenL) {
            res[k++] = left[i++];
        }
        while (j < lenR) {
            res[k++] = right[j++];
        }
        return res;
    }

    private static void printList(int[] list) {
        for (int i1 : list) {
            System.out.print(i1 + ",");
        }
        System.out.println();
    }
}
